package LeetcodeTest_thirty;
//46.全排列

import java.util.ArrayList;
import java.util.List;

public class permute
{
    public static void main(String[] args)
    {
        int[] nums={1,2,3};
        List<List<Integer>> solutions=new ArrayList<List<Integer>>();
        solutions=solution.permute(nums);
        for(List<Integer> values:solutions)
        {
            for(Integer value:values)
                System.out.print(value+" ");
            System.out.println();
        }
    }
}
class solution
{
    public static List<List<Integer>> permute(int[] nums)
    {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        List<Integer> temp=new ArrayList<>();
        backtrace(result,temp,nums);
        return result;
    }
    public static void backtrace(List<List<Integer>> result,List<Integer> memory,int[] nums)
    {
        List<Integer> answer=new ArrayList<>(memory);
        if(answer.size()==nums.length)
        {
            result.add(answer);
            return;
        }
        else
        {
            for(int i=0;i<nums.length;i++)
            {
                if(!answer.contains(nums[i]))
                {
                    answer.add(nums[i]);
                    backtrace(result,answer,nums);
                    answer.remove(answer.size()-1);
                }
            }
        }

    }
}